package codeTopPractice;

import codeTopPractice.sortedPractice.快排;

import java.util.Arrays;
import java.util.Random;

/**
 * @LeetCode 第215题
 *
 * 第一种解法
 * 本人写出了近乎无脑的解法，用循环判断是否每个元素都大于后一个元素，得出是否排序完成的方法isSorted()
 * 以是否完成排序为条件进行while循环，依次把前后顺序不对应的两个元素交换位置，直至全部交换成功
 * 该解法比较常规，逻辑上没有错误，但是不能通过leetcode极端案例测试（万级别以上的数字个数），超过时间限制未通过
 *
 * 第二种解法
 * 暴力解法，通过自带API方法进行排序最后输出
 *
 * 第三种解法
 * 最佳解法，官方的基于快速排序的快速选择方法
 * 附上快速排序算法
 *
 */


public class 数组中第k个最大的元素 {

    public static void main(String[] args) {

    }

//    //无脑解法
      //超时不通过
//    public int findKthLargestMyMethod(int[] nums ,int k){
//
//        if (nums.length <= 1){
//            return nums[k-1];
//        }
//
//        while (!isSorted(nums)){
//            for (int i = 0; i < nums.length - 1 ; i++) {
//                if (nums[i] < nums[i+1]){
//                    int temp = nums[i];
//                    nums[i] = nums[i+1];
//                    nums[i+1] = temp;
//                }
//            }
//        }
//        return nums[k-1];
//    }
//
//    public boolean isSorted(int[] nums){
//        Boolean isOK = false;
//        for (int i = 0; i < nums.length - 1; i++) {
//            if (nums[i] < nums[i+1]){
//                isOK = false;
//                break;
//            }else {
//                isOK = true;
//            }
//        }
//        return isOK;
//    }
//


//    //暴力解法 利用JAVA的api
//    //leetcode执行用时：24ms  消耗内存： 48.6MB
//    public int findKthLargestBoom(int[] nums, int k) {
//        int len = nums.length;
//        Arrays.sort(nums);
//        return nums[len - k];
//    }


    //快排
    //用时 89ms  内存 48.6MB
    public int quickSortedAndReturn(int[] nums, int k){
        快排 kp = new 快排();
        kp.quickSorted(nums,0,nums.length-1);
        return nums[k-1];
    }

    //本人写的快速选择
    //用时：15ms， 内存49.1MB
    public static int solution(int[] nums, int k){

        return myQuickSelect(nums,0,nums.length-1,k);
    }

    public static int myQuickSelect(int[] array, int l ,int r,int k){

        if(array.length == 1){
            return array[l];
        }


        int start = l;
        int end = r;

        int key = array[l];

        while (end > start) {
            while (end > start && array[end] >= key) end--;
            while (end > start && array[start] <= key) start++;
            int temp = array[end];
            array[end] = array[start];
            array[start] = temp;
        }
        array[l] = array[end];
        array[end] = key;

        if (end == array.length-k){
            return array[array.length-k];
        }

        if(end < array.length-k){
            return myQuickSelect(array,end+1, r, k);
        }else {
            return myQuickSelect(array,l,end-1,k);
        }

    }

    //官方最佳解法：快速选择
    //用时：5ms， 内存49MB

    Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    public int quickSelect(int[] a, int l, int r, int index) {
        int q = randomPartition(a, l, r);
        if (q == index) {
            return a[q];
        } else {
            return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
        }
    }

    public int randomPartition(int[] a, int l, int r) {
        int i = random.nextInt(r - l + 1) + l;
        swap(a, i, r);
        return partition(a, l, r);
    }

    public int partition(int[] a, int l, int r) {
        int x = a[r], i = l - 1;
        for (int j = l; j < r; ++j) {
            if (a[j] <= x) {
                swap(a, ++i, j);
            }
        }
        swap(a, i + 1, r);
        return i + 1;
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }




}
